CWOI20231024A 赢钱

简要题意：

初始有 $A$ 元钱，然后每次可以花费 $x$ （$0 < x < \text{当前钱数}, x \in \mathbb{R}$）元，有 $P$ 的概率获得 $2x$ 元，$1 - P$ 的概率不获得钱。问获得 $B$（$B > A$）元的概率。对 $998244353$ 取模。

首先若 $P > 0.5$，答案是 $1$，因为假如你每次投入 $\varepsilon$ 元，当 $\varepsilon \to 0$ 时，若投入 $x$ 元，应增加 $Px$ 元，而减少 $(1 - P)x$ 元，总共增加 $(2P - 1)x$ 元，那么钱数总是在增多的，那么必定可以达到 $B$。

现在来解决 $P\leq 0.5$。有一个神奇的地方在于，若规定只玩 $m$ 轮，可以将 $B$ 划分成 $2^m$ 段，每段内部概率相同。就拿样例来说：$B = 4, P = 0.3$。若只玩 $1$ 轮，那么，$x\in [0, 2)$ 成功的概率是 $0$，$x\in [2, 4)$ 成功的概率是 $P = 0.3$。若只玩 $2$ 轮，那么，$x\in [0, 1)$ 成功的概率是 $0$，$x\in [1, 2)$ 成功的概率是 $P^2 = 0.09$，$x\in[2, 3)$ 成功的概率是 $P = 0.3$，$x\in[3, 4)$ 成功的概率是 $P + (1 - P)\cdot P = 0.51$。

我们可以把 $\frac AB$ 用一个二进制小数表示，来区分每个段。只玩前 $i$ 位小数，就是只玩 $i$ 轮。

考虑从后往前 dp。 我们记 $f[i]$ 表示只玩小数点后第 $i$ 位及以后的，希望能玩到“向第 $i-1$ 位进位” ，成功的概率是多少。显然，$f[1]$ 就是答案。转移的话，分第 $i$ 位为 $0/1$ 讨论。 如果第 $i$ 位为 $0$，那么 $f[i]=f[i+1]\cdot p$，也就是必须下一位能进位，并且再玩一次才能进位。否则，$f[i]=f[i+1]+(1-f[i+1])\cdot p$，表示如果下一位成功进位了，由于这一位是 $1$，能直接再往前进，否则的话需要玩一次，能获得 $2x$ 元则能进位。

但是这只能解决 $B\mid 2^n \times A$ 的情况，也就是 $A$ 在某个整段的端点上。否则 $\frac AB$ 是一个无限循环小数。

但是循环小数好啊。考虑求循环节的过程（竖式模拟除法），发现，若当前被除数是 $A'$，且之前存在过一个 $A'' = A'$ 那么就有一个循环节。由于除数 $B$ 不变，所以 $A''$ 和 $A'$ 可以理解为解决了同一个问题！

那么，设这个循环节起始位置是 $p$，终止位置是 $q$（$a_{q+1} = a_p$）那么有 $f[q+1] = f[p]$。

这就是一个线性方程。$f[q+1]$ 可以线性地推到 $f[p]$。具体地，设 $x=f[q+1]$，有 $f[q+1] = 1x + 0$。若 $f[i+1]=kx + b$，那么 $f[i] = \lambda (kx + b) + \eta$（$\lambda$ 和 $\eta$ 都是一个系数）。自然可以推出 $f[p] = mx+n$。求解 $mx + n = x$ 即可得到 $f[q + 1]$。然后就是一个有限的 dp 问题了，简单求解即可。

代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int P = 998244353, Q = 616898040;

int a, z, q, i, j;
int vis[2000008];
bitset<2000008> tp;

int Qpow(int x, int y) 
{
    int ret = 1; 
    for (; y; y >>= 1) {
        if (y & 1) ret = ret * x % P;
        x = x * x % P;
    }
    return ret;
}

signed main() 
{
    cin >> a >> z >> q;
    for (i = 1; !vis[a]; i++) {
        vis[a] = i;
        a = a + a;
        if (a >= z) a -= z, tp.set(i);
    }
    int k = 1, b = 0, p = q * Q % P; q = 1 + P - p;
    for (j = vis[a], i--; i >= j; i--) {
        if (tp[i]) k = k * q % P, b = (b * q + p) % P;
        else k = k * p % P, b = b * p % P;
    }
    k = (P - b) * Qpow(k - 1, P - 2) % P;
    while (--j) {
        if (tp[j]) k = (p + q * k) % P;
        else k = p * k % P;
    }
    cout << k << '\n';
    return 0;
}